import java.util.*;


public class Solution10 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @param size int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        // write code here
        if(size < 1){
            return res;
        }
        Deque<Integer> deque = new LinkedList<>();
        

        //第一个窗口加进来
        for(int i = 0;i<size && i < num.length;i++){
            if(deque.size() == 0){
                deque.offerLast(num[i]);
            } else {
                int count = 1;
                while(!deque.isEmpty() && deque.peekLast() < num[i]){
                    deque.pollLast();
                    count++;
                }
                while(count > 0){
                    count--;
                    deque.offerLast(num[i]);
                }
            }
        }
        //窗口移动
        for(int i = size;i<num.length;i++){
            res.add(deque.pollFirst());
            int count = 1;
            while(!deque.isEmpty() && deque.peekLast() < num[i]){
                deque.pollLast();
                count++;
            }
            while(count > 0){
                count--;
                deque.offerLast(num[i]);
            }
        }
        if(deque.size() == size){
            res.add(deque.pollFirst());
        }
        return res;
    }
}